A-Normal Form
#ラムダ計算
letを除くすべての項が副項を持たないように書いていく方式｡特に関数型言語向けコンパイラの中間言語として､CPS (continuation-passing style, 継続渡し方式)と並ぶ存在｡
ANFはチューリング完全だったとおもう
副項を持たないようにするために､let式を用いて副項になる部分を変数に束縛していく｡この点からSSAと非常に類似している｡
基本例
code:haskell
f $ g $ h $ v
===
let x1 = h v in
let x2 = g x1 in
let x3 = f x2 in
x3
型なしラムダ計算のANF変換
ナイーブにやると2-passの変換になるけどdelimited continuationを使うと1passで済む｡
読者への課題とする nymphium.icon誰か書いてくれ〜
利用例
Haskellのdo
pure computationを一つの項と捉え､他の演算子とかを省くと､computationの結果を逐一変数に代入しておりANFと考えられる
参考文献
Kennedy, Andrew. Compiling with Continuations, Continued. ACM SIGPLAN International Conference on Functional Programming, 2007.